#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <iostream>
#include <time.h>
using namespace std;

//快速排序（王道）
class QuickSort
{
public:
    int Partition(vector<int> &nums, int low, int high)
    {
        int pivot = nums[low]; //首先使用左边变量存储分割值
        while (low < high)
        {
            while (low < high && nums[high] >= pivot) //从后往前遍历，找到一个比分割值小的
                --high;
            nums[low] = nums[high];                  //把比分隔值小的那个元素，放到 nums[low]
            while (low < high && nums[low] <= pivot) //从前往后遍历，找到一个比分割值大的
                ++low;
            nums[high] = nums[low]; //把比分隔值大的那个元素，放到 nums[high],因为刚才 high 位置的元素已经放到了 low 位置
        }
        nums[low] = pivot;
        return low; //返回分隔值所在的下标
    }

    void QuickSort0(vector<int> &nums, int low, int high)
    {
        if (low < high)
        {
            int pivotpos = Partition(nums, low, high); //分割点左边的元素都比分割点要小，右边的比分割点大
            QuickSort0(nums, low, pivotpos - 1);
            QuickSort0(nums, pivotpos + 1, high);
        }
    }

    vector<int> sortVector(vector<int> &nums)
    {
        int low = 0;
        int high = nums.size() - 1;
        QuickSort0(nums, low, high);
        return nums;
    }
};

class MyVector
{
public:
    vector<int> InitVector()
    {
        vector<int> v;
        int i;
        srand(time(NULL)); //随机数生成，每一次执行代码就会得到随机的 10 个元素
        int l = rand() % 15 + 1;
        for (i = 0; i < l; i++)
        {
            v.push_back(rand() % 100); //生成的是 0-99 之间
        }
        return v;
    }

    void PrintVector(vector<int> v)
    {
        for (int i = 0; i < v.size(); i++)
        {
            printf("%3d", v[i]);
        }
        printf("\n");
    }
};

int main()
{
    MyVector temp;
    vector<int> v = temp.InitVector();
    temp.PrintVector(v);
    QuickSort s;
    temp.PrintVector(s.sortVector(v));
    system("pause");
    return 0;
}